#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// 方向

const int DIR4[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
const int DIR8[8][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};

// 一些工具函数

// 更新最大最小值
template <class T>
bool chkmin(T &x, const T &y) { return y < x ? x = y, 1 : 0; }
template <class T>
bool chkmax(T &x, const T &y) { return x < y ? x = y, 1 : 0; }